package com.pekExercises;

import java.util.Arrays;
import java.util.Random;

/**
 * 一个数的序列ai，当a1 < a2 < ... < aS的时候，我们称这个
 * 序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可
 * 以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 <
 * i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，
 * 有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序
 * 列中最长的长度是4，比如子序列(1, 3, 5, 8).
 * 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
 */
public class MaxSubsequence {


    public static int getMaxSubsequence(int[] input){
        int[] tmpInfo = new int[input.length];
        int[] maxInfo = new int[input.length];
        return getMaxSubsequenceInner(input,input.length - 1,tmpInfo);
    }

    private static int getMaxSubsequenceInner(int[] input, int end,int[] tmpInfo) {

        tmpInfo[0] = 1;

        for(int i = 1;i <= input.length - 1;i ++){

            int max = 1;
            for(int j = 0;j < i;j ++){
                int t = tmpInfo[j];
                //大于时才去沿着更新，小于时不更新。
                if(input[j] < input[i]){
                   t ++;
                   if(t > max){
                       max = t;
                   }
                }
            }
            tmpInfo[i] = max;

            //maxInfo[i] = Math.max(maxInfo[i - 1],input[i]);

        }

        int res = 0;
        for(int i : tmpInfo){
            if(i > res){
                res = i;
            }
        }
        return res;

    }

    public static void main(String[] args){

        int count = 10;
        int range = 100;

        Random random = new Random();

        int[] input = new int[count];
        for(int i = 0;i < count;i ++){
            input[i] = random.nextInt(range);
        }



        System.out.println(getMaxSubsequence(input));
        System.out.println(Arrays.toString(input));

    }
}
